import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。
 * 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
 *
 * Date: 2022-09-29
 * Time: 15:40
 */



public class Algorithm {

    public static int MoreThanHalfNum_Solution(ArrayList<Integer> array) {

        /*
        // 法一: 定义map，使用<数字，次数>的映射关系，最后统计每个字符出现的次数
        if(array == null) {
             return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < array.size(); i++){

            if(map.containsKey(array.get(i))){
                int count = map.get(array.get(i));
                count++;
                map.put(array.get(i), count);
            } else{
                map.put(array.get(i), 1);
            }

            if(map.get(array.get(i)) > array.size()/2){

                return array.get(i);
            }
        }
        return 0;
        */

        //  法三: 同时去掉两个不同的数字. [这是重点掌握.]
        if(array == null) { return 0; }

        int result = array.get(0);
        int times = 1;

        for(int i = 1; i < array.size(); ++i) {
            if(times == 0) {
                result = array.get(i);
                times = 1;
            } else if(result == array.get(i)) {
                times++;
            } else {
                times--;
            }
        }
        // 判断是不是真的存在.
        int count = 0;
        for (Integer integer : array) {
            if (integer == result) {
                count++;
            }
        }
        return count > (array.size() >> 1) ? result : 0;
    }

    //  法二: 排序，出现次数最多的数字，一定在中间位置。然后检测中间出现的数字出现的次数是否符合要求
    public static int MoreThanHalfNum_Solution(int[] array) {
        Arrays.sort(array);
        int half = array.length >> 1;
        int target = array[half];
        for (int j : array) {
            if (target == j) {
                half--;
            }
            if(half < 0) {
                return j;
            }
        }
        return 0;
    }

    public static void main(String[] args) {

        // 顺序表用来测试法一 法三
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(2);
        arrayList.add(2);
        arrayList.add(2);
        arrayList.add(5);
        arrayList.add(4);
        arrayList.add(2);
        System.out.println(MoreThanHalfNum_Solution(arrayList));

        // 数组测试方法二
        int[] array = {1,2,3,2,2,2,5,4,2};
        System.out.println(MoreThanHalfNum_Solution(array));
    }
}
